TNotes.leetcode

Appearance

⏰0756. 金字塔转换矩阵【中等】

0756. 金字塔转换矩阵【中等】 ​

1. 📝 题目描述 ​

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行 少一个块，并且居中。

为了使金字塔美观，只有特定的 三角形图案 是允许的。一个三角形的图案由 两个块 和叠在上面的 单个块 组成。模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。

  • 例如，"ABC" 表示一个三角形图案，其中一个 “C” 块堆叠在一个 'A' 块(左)和一个 'B' 块(右)之上。请注意，这与 "BAC" 不同，"B" 在左下角，"A" 在右下角。

你从作为单个字符串给出的底部的一排积木 bottom 开始，必须 将其作为金字塔的底部。

在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的 每个三角形图案 都是在 allowed 中的，则返回 true，否则返回 false。

示例 1：

img

txt
输入：bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
输出：true
解释：允许的三角形图案显示在右边。
从最底层(第 3 层)开始，我们可以在第 2 层构建“CE”，然后在第 1 层构建“E”。
金字塔中有三种三角形图案，分别是 “BCC”、“CDE” 和 “CEA”。都是允许的。

示例 2：

img

txt
输入：bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
输出：false
解释：允许的三角形图案显示在右边。
从最底层(即第 4 层)开始，创造第 3 层有多种方法，但如果尝试所有可能性，你便会在创造第 1 层前陷入困境。

提示：

  • 2 <= bottom.length <= 6
  • 0 <= allowed.length <= 216
  • allowed[i].length == 3
  • 所有输入字符串中的字母来自集合 {'A', 'B', 'C', 'D', 'E', 'F'}。
  • allowed 中所有值都是 唯一的

2. 🎯 s.1 - 回溯 ​

c
char map[26][26][8]; // map[a][b] = possible chars on top
int mapSize[26][26];

bool build(char* row, int len) {
    if (len == 1) return true;
    char next[len];
    return dfs(row, len, next, 0);
}

bool dfs(char* row, int len, char* next, int i) {
    if (i == len - 1) {
        next[i] = '\0';
        return build(next, len - 1);
    }
    int a = row[i] - 'A', b = row[i + 1] - 'A';
    for (int k = 0; k < mapSize[a][b]; k++) {
        next[i] = map[a][b][k];
        if (dfs(row, len, next, i + 1)) return true;
    }
    return false;
}

bool pyramidTransition(char* bottom, char** allowed, int allowedSize) {
    memset(mapSize, 0, sizeof(mapSize));
    for (int i = 0; i < allowedSize; i++) {
        int a = allowed[i][0] - 'A', b = allowed[i][1] - 'A';
        map[a][b][mapSize[a][b]++] = allowed[i][2];
    }
    return build(bottom, strlen(bottom));
}
js
/**
 * @param {string} bottom
 * @param {string[]} allowed
 * @return {boolean}
 */
var pyramidTransition = function (bottom, allowed) {
  const map = new Map()
  for (const s of allowed) {
    const key = s[0] + s[1]
    if (!map.has(key)) map.set(key, [])
    map.get(key).push(s[2])
  }
  const build = (row) => {
    if (row.length === 1) return true
    const nexts = []
    const dfs = (i, cur) => {
      if (i === row.length - 1) return build(cur)
      const key = row[i] + row[i + 1]
      const chars = map.get(key) || []
      for (const c of chars) {
        if (dfs(i + 1, cur + c)) return true
      }
      return false
    }
    return dfs(0, '')
  }
  return build(bottom)
}
py
class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        from collections import defaultdict
        mp = defaultdict(list)
        for s in allowed:
            mp[s[:2]].append(s[2])
        def build(row):
            if len(row) == 1:
                return True
            def dfs(i, cur):
                if i == len(row) - 1:
                    return build(cur)
                for c in mp[row[i] + row[i + 1]]:
                    if dfs(i + 1, cur + c):
                        return True
                return False
            return dfs(0, '')
        return build(bottom)
  • 时间复杂度：O(An)，其中 A 是字母表大小，n 是 bottom 长度
  • 空间复杂度：O(n2)，递归栈深度

算法思路：

  • 用哈希表存储每对相邻字母可生成的字母
  • 递归构建每一层，对每个位置枚举可能的字母
  • 成功构建到只剩 1 个字母时返回 true